package nachos.vm;

import java.util.Hashtable;

import nachos.machine.CoffSection;
import nachos.machine.Lib;
import nachos.machine.Machine;
import nachos.machine.Processor;
import nachos.machine.TranslationEntry;

/**
 * This class implement a inverted page table for all processes of the system. 
 * 
 *
 * @author Sylvia
 *
 */
public class PagingManager {
	
	/**
	 * While a TLBMiss occur, this function looks up the page table, 
	 * return a Translation directly if the item exists in the page 
	 * table, or handle the page fault if doesn't.
	 * there may be two possibilities that we cannot find page in the
	 *  page table:
	 * <ul>1.we can find it in the swap file, exchange it in then.</ul>
	 * <ul>2.we cannot find it in the swap file either, then it must hasn't
	 *  be loaded yet.</ul>
	 * 
	 * @param	pid	the process id calling page fault
	 * @param	vpn	the virtual number of the page looking after.
	 * @return a TranslationEntry object for TLB to update
	 */
	public static TranslationEntry lookUp(int pid, int vpn){
		Lib.debug(VMProcess.dbgVM, "look up in page table : pid = " + pid + " vpn = " + vpn);
		KeyItem ki = new KeyItem(pid, vpn);
		int tpid = -1;
		
		printPagetable();
		printInvertedTable();
		
		// if already exists in the page table
		if (invertedTable.containsKey(ki)){
			// return the translation entry directly
			int pp = invertedTable.get(ki);
			TranslationEntry temp = pageTable.get(pp);
			Lib.debug(VMProcess.dbgVM, "\tfound and return this page : vpn = " + temp.vpn + " ppn = " + temp.ppn);
			pageTableAlgo.informUsePosition(temp.ppn);
			return new TranslationEntry(temp);
		}
		
		// if doesn't exist in the page table
		else{
			pageFaultCount ++;
			// step 1.find a position to write in the new page
			int ppn;
			if (pageTableAlgo.hasFreePosition()){
				//pageTableAlgo.printCounters();
				//pageTableAlgo.printFreePos();
				ppn = pageTableAlgo.getFreePosition();				
				Lib.assertTrue(!pageLocked[ppn]);
				lockPage(ppn);
				
			}
			else{
				// find a best position
				//pageTableAlgo.printCounters();
				//pageTableAlgo.printFreePos();
				ppn = pageTableAlgo.getBestPosition();				
				Lib.debug(VMProcess.dbgVM, "find a position to exchange : " + ppn);				
				Lib.assertTrue(!pageLocked[ppn]);
				lockPage(ppn);
				
				// if it has been modified, write it back first
				TranslationEntry _te = new TranslationEntry(pageTable.get(ppn));
				for (KeyItem _ki : invertedTable.keySet()){
					if (invertedTable.get(_ki) == ppn)
						tpid = _ki.processID;
				}
				Lib.assertTrue(tpid != -1);
				if (!SwapManager.exists(tpid, _te.vpn) || _te.dirty){
					Lib.debug(VMProcess.dbgVM, "write back this page first.");										
					SwapManager.write(tpid, _te.vpn, ppn);					
				}
				
				// if this page's in the TLB, set invalid
				for (int i = 0; i < Machine.processor().getTLBSize(); i ++){
					TranslationEntry entry = Machine.processor().readTLBEntry(i); 
					if (entry.ppn == ppn && entry.valid == true){
						entry.valid = false;
						Machine.processor().writeTLBEntry(i, entry);
						Lib.debug(VMProcess.dbgVM, "set TLB item invalid: ppn = " + ppn);
					}
				}
				
				// remove from the invertedTable
				if (invertedTable.containsValue(ppn)){
					for (KeyItem _ki : invertedTable.keySet()){
						if (invertedTable.get(_ki) == ppn){
							invertedTable.remove(_ki);
							Lib.debug(VMProcess.dbgVM, "remove from the inverted table.");
							break;
						}							
					}
				}
			}
			
			// step2.exchange or load?
			TranslationEntry te = new TranslationEntry();
			// if the target page is in the swap disk, exchange it in!
			if (SwapManager.exists(pid, vpn)){
				Lib.debug(VMProcess.dbgVM, "\tneed exchange from swap file!!");
				byte[] buf = new byte[Processor.pageSize]; 
				TranslationEntry tempTe = SwapManager.getPage(pid, vpn, buf);
				te.ppn = ppn;
				te.vpn = tempTe.vpn;
				te.readOnly = tempTe.readOnly;
				System.arraycopy(
						buf, 0, Machine.processor().getMemory(), ppn*Processor.pageSize, Processor.pageSize);
				Lib.debug(VMProcess.dbgVM, "\texchange from swap file");
			}
			// if does not, then it must be the first time to load in the page
			else{
				// load the page, get the TranlationEntry object
				Lib.debug(VMProcess.dbgVM, "\thasn't load yet, pid = " + pid + " vpn = " + vpn);
				te = loadPage(pid, vpn, ppn);
			}
			
			// step3.update page table
			// refer to the page table
			invertedTable.put(new KeyItem(pid, vpn), ppn);
			//Lib.debug(VMProcess.dbgVM, "new invertedtable : " + invertedTable);
			pageTable.put(ppn, te);
			//Lib.debug(VMProcess.dbgVM, "new pageTable : " + pageTable);
			pageTableAlgo.informUsePosition(ppn);
			
			unlockPage(ppn);
			
			return new TranslationEntry(te);
			
		}
	}
	
	public static void lockPage(int ppn){
		//lock this page
		pageLocked[ppn] = true;
		pageTableAlgo.lockPos(ppn);
	}
	
	public static void unlockPage(int ppn){
		//unlock this page
		Lib.assertTrue(pageLocked[ppn]);
		pageTableAlgo.unlockPos(ppn);
		pageLocked[ppn] = false;
	}
	
	public static boolean isLocked(int ppn){
		Lib.assertTrue(!pageLocked[ppn]);
		return pageLocked[ppn];
	}
	
	public static void informDirty(int ppn){
		pageTable.get(ppn).dirty = true;
	}
	
	public static void informUsed(int ppn){
		pageTableAlgo.informUsePosition(ppn);
	}
	
	private static void printInvertedTable() {
		Lib.debug(VMProcess.dbgVM, "print inverted table:");
		//System.out.print("inverted table: ");
		for (KeyItem ki : invertedTable.keySet()){
			Lib.debug(VMProcess.dbgVM, "  pid = " + ki.processID + " vpn = " + ki.vpn + " ppn = "+ invertedTable.get(ki));
			//System.out.print("  pid = " + ki.processID + " vpn = " + ki.vpn + " ppn = "+ invertedTable.get(ki) + "\t");
		}
		//System.out.println();
	}

	private static void printPagetable(){
		Lib.debug(VMProcess.dbgVM, "print page table:");
		//System.out.print("print page table: ");
		for (int i : pageTable.keySet()){
			Lib.debug(VMProcess.dbgVM, "  ppn = " + i + " vpn = " + pageTable.get(i).vpn);
			//System.out.print("  ppn = " + i + " vpn = " + pageTable.get(i).vpn + "\t");
		}
		//System.out.println();
	}
	 
	/**
	 * first load
	 */
	static private TranslationEntry loadPage(int pid, int vpn, int ppn){		
		// get the loading information, be sure that this 
		// page has register for lazy loading before.
		Lib.assertTrue(pageLocked[ppn]);
		Lib.debug(VMProcess.dbgVM, 
				"\t\tfirst load : pid = " + pid + "    loading in vpn = " + vpn + " to ppn = " + ppn);
		LazyLoadingPageItem pi = lazyLoadingInfo.get(new KeyItem(pid, vpn));
		Lib.assertTrue(pi != null);
		if (pi.needSectionLoad)
			Lib.debug(VMProcess.dbgVM, "section : " + pi.section.getName() + " spn = " + pi.spn);
		else
			Lib.debug(VMProcess.dbgVM, "stack or argu page");
		Lib.assertTrue(pi != null);
				
		// initialize a blank page
		byte[] memory = Machine.processor().getMemory();
		int from = Processor.pageSize * ppn;
		int to = from + Processor.pageSize;
		for (int i = from; i < to; i ++)
			memory[i] = 0;
		
		TranslationEntry te = new TranslationEntry();
		te.ppn = ppn;
		te.vpn = vpn;
		te.used = true;
		te.valid = true;
		
		// code sections
		if (pi.needSectionLoad && pi.section.getName().equals(".text")){
			te.readOnly = true;
			Lib.debug(VMProcess.dbgVM, "readonly!");
		}
		else{
			te.readOnly = false;
		}
		
		if (pi.needSectionLoad)
			pi.section.loadPage(pi.spn, ppn);
		
		Lib.debug(VMProcess.dbgVM, "\t\tload successfully!");
		return new TranslationEntry(te);
	}
	
	/**
	 * Simply login a lazyLoadingPage's information instead of loading all pages, 
	 * each page would not be loaded until page fault occurred, then, the 
	 * PagingManager will call <code>load()</code> to load this page.   
	 * @param pid processID
	 * @param vpn virtual page number in this process
	 * @param section CoffSection object this page's referring to
	 * @param spn inner page number of the section
	 * @param isStackPage true if it's a stack page
	 */
	static public void lazy(
			int pid, int vpn, 
			CoffSection section, int spn, 
			boolean needSectionLoad){
		lazyLoadingInfo.put(
				new KeyItem(pid, vpn), 
				new LazyLoadingPageItem(section, spn, needSectionLoad));
		if (needSectionLoad){
			Lib.debug(VMProcess.dbgVM, "lazy loading : pid = " + pid + " section name = " + section.getName() +
					" spn = " + spn + " vpn = " +  vpn + " needSectionLoad = " + needSectionLoad);
		}
		else{
			Lib.debug(VMProcess.dbgVM, "lazy loading : pid = " + pid + " vpn = " +  vpn + " needSectionLoad = " + needSectionLoad);
		}
	}
	
	/**
	 * set a ppn dirty
	 * @param ppn
	 */
	static public void setPageDirty(int ppn){
		pageTable.get(ppn).dirty = true;
	}
	
	static public boolean isCodePage(int ppn){
		return (pageTable.get((Integer)ppn).readOnly);
	}
	
	static public void printPageFaultCount(){
		System.out.println("page fault number = " +  pageFaultCount);
	}
	
	/** the algorithm part of the page table */
	static private FreePositionManager pageTableAlgo;
	
	/** number of the physic pages */
	static private int numPage;
	
	static private int pageFaultCount = 0;
	
	/**
	 * inverted page table 
	 * key : process id and vpn 
	 * value : ppn 
	 * */
	static private Hashtable<KeyItem, Integer> invertedTable;
	
	/**
	 * page table
	 * key : ppn
	 * value : the target TranslationEntry
	 */
	static public Hashtable<Integer, TranslationEntry> pageTable;
	
	static private Hashtable<KeyItem, LazyLoadingPageItem> lazyLoadingInfo;
	
	static private boolean[] pageLocked;
	
	
	static {
		numPage = Machine.processor().getNumPhysPages();
		pageTableAlgo = new FreePositionManager(numPage);
		invertedTable = new Hashtable<KeyItem, Integer>();
		pageTable = new Hashtable<Integer, TranslationEntry>();
		lazyLoadingInfo = new Hashtable<KeyItem, LazyLoadingPageItem>();
		pageLocked = new boolean[numPage];
		for (int i = 0; i < numPage; i ++){
			pageLocked[i] = false;
		}
	}
}

class KeyItem{
	public KeyItem(int _processID, int _vpn){
		processID = _processID;
		vpn = _vpn;
	}
	
	@Override
	public boolean equals(Object o){
		KeyItem oo = (KeyItem) o;
		return (oo.processID == this.processID && oo.vpn == this.vpn);
	}
	
		
	public int hashCode(){
		return processID*100000+vpn;		
	}
	
	public int processID;
	public int vpn;
}

class LazyLoadingPageItem{
	public LazyLoadingPageItem(CoffSection _section, int _spn, boolean _is){
		section = _section;
		spn = _spn;
		needSectionLoad = _is;
	}
	
	public boolean equals(Object obj) {
		LazyLoadingPageItem o = (LazyLoadingPageItem)obj;
		if (!this.section.equals(o.section) ||
				!(this.spn == o.spn) ||
				!(this.needSectionLoad == o.needSectionLoad))
			return false;
		return true;
	};
	
	CoffSection section;
	int spn;
	boolean needSectionLoad;
}
